
<!DOCTYPE html>

<html>
  
<!-- Mirrored from docs.sympy.org/latest/modules/combinatorics/pc_groups.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:28:18 GMT -->
<!-- Added by HTTrack --><meta http-equiv="content-type" content="text/html;charset=utf-8" /><!-- /Added by HTTrack -->
<head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>Polycyclic Groups &#8212; SymPy 1.9 documentation</title>
    <link rel="stylesheet" type="text/css" href="../../_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/default.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/graphviz.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/plot_directive.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-core.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-autocomplete.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-sphinx.css" />
    
    <script data-url_root="../../" id="documentation_options" src="../../_static/documentation_options.js"></script>
    <script src="../../_static/jquery.js"></script>
    <script src="../../_static/underscore.js"></script>
    <script src="../../_static/doctools.js"></script>
    <script src="../../../../live.sympy.org/static/utilities.js"></script>
    <script src="../../../../live.sympy.org/static/external/classy.js"></script>
    <script src="../../../../live.sympy.org/static/live-core.js"></script>
    <script src="../../../../live.sympy.org/static/live-autocomplete.js"></script>
    <script src="../../../../live.sympy.org/static/live-sphinx.js"></script>
    <script async="async" src="../../../../cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest8331.js?config=TeX-AMS_HTML-full"></script>
    <script type="text/x-mathjax-config">MathJax.Hub.Config({"tex2jax": {"inlineMath": [["\\(", "\\)"]], "displayMath": [["\\[", "\\]"]]}})</script>
    
    <link rel="shortcut icon" href="../../_static/sympy-notailtext-favicon.ico"/>
    <link href="pc_groups.html" rel="canonical" />
    
    <link rel="index" title="Index" href="../../genindex.html" />
    <link rel="search" title="Search" href="../../search.html" />
    <link rel="next" title="Concrete" href="../concrete.html" />
    <link rel="prev" title="Finitely Presented Groups" href="fp_groups.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="../concrete.html" title="Concrete"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="fp_groups.html" title="Finitely Presented Groups"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="index.html" accesskey="U">Combinatorics</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Polycyclic Groups</a></li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="polycyclic-groups">
<h1>Polycyclic Groups<a class="headerlink" href="#polycyclic-groups" title="Permalink to this headline">¶</a></h1>
<section id="introduction">
<h2>Introduction<a class="headerlink" href="#introduction" title="Permalink to this headline">¶</a></h2>
<p>This module presents the functionality designed for computing with
polycyclic groups(PcGroup for short). The name of the corresponding
SymPy object is <code class="docutils literal notranslate"><span class="pre">PolycyclicGroup</span></code>. The functions or classes described
here are studied under <strong>Computational Group Theory</strong>.</p>
<section id="overview-of-functionalities">
<h3>Overview of functionalities<a class="headerlink" href="#overview-of-functionalities" title="Permalink to this headline">¶</a></h3>
<ul class="simple">
<li><p>The construction of PolycyclicGroup from a given PermutationGroup.</p></li>
<li><p>Computation of polycyclic generating sequence(pcgs for short) and
polycyclic series(pc_series).</p></li>
<li><p>Computation of relative order for polycyclic series.</p></li>
<li><p>Implementation of class Collector which can be treated as a base for polycylic groups.</p></li>
<li><p>Implementation of polycyclic group presentation(pc_presentation for short).</p></li>
<li><p>Computation of exponent vector, depth and leading exponent for a given element
of a polycyclic group.</p></li>
</ul>
<p>For a description of fundamental algorithms of polycyclic groups, we
often make use of <em>Handbook of Computational Group Theory</em>.</p>
</section>
</section>
<section id="the-construction-of-polycyclic-groups">
<h2>The Construction of Polycyclic Groups<a class="headerlink" href="#the-construction-of-polycyclic-groups" title="Permalink to this headline">¶</a></h2>
<p>Given a Permutation Group, A Polycyclic Group is constructed by computing the
corresponding polycylic generating sequence, polycyclic series and it’s
relative order.</p>
<section id="attributes-of-polycyclicgroup">
<h3>Attributes of PolycyclicGroup<a class="headerlink" href="#attributes-of-polycyclicgroup" title="Permalink to this headline">¶</a></h3>
<ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">pc_sequence</span></code> : Polycyclic sequence is formed by collecting all the missing
generators between the adjacent groups in the derived series of given
permutation group.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">pc_series</span></code> : Polycyclic series is formed by adding all the missing generators
of <code class="docutils literal notranslate"><span class="pre">der[i+1]</span></code> in <code class="docutils literal notranslate"><span class="pre">der[i]</span></code>, where <code class="docutils literal notranslate"><span class="pre">der</span></code> represents derived series.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">relative_order</span></code> : A list, computed by the ratio of adjacent groups in pc_series.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">collector</span></code> : By default, it is None. Collector class provides the polycyclic presentation.</p></li>
</ul>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">len</span><span class="p">(</span><span class="n">PcGroup</span><span class="o">.</span><span class="n">pcgs</span><span class="p">)</span>
<span class="go">4</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">pc_series</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">pc_series</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">pc_series</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">==</span><span class="n">G</span>
<span class="go">True</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">gen</span> <span class="o">=</span> <span class="n">pc_series</span><span class="p">[</span><span class="nb">len</span><span class="p">(</span><span class="n">pc_series</span><span class="p">)</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">generators</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">gen</span><span class="o">.</span><span class="n">is_identity</span>
<span class="go">True</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span><span class="o">.</span><span class="n">relative_order</span>
<span class="go">[2, 3, 2, 2]</span>
</pre></div>
</div>
</section>
</section>
<section id="the-construction-of-collector">
<h2>The Construction of Collector<a class="headerlink" href="#the-construction-of-collector" title="Permalink to this headline">¶</a></h2>
<p>Collector is one of the attributes of class PolycyclicGroup.</p>
<section id="attributes-of-collector">
<h3>Attributes of Collector<a class="headerlink" href="#attributes-of-collector" title="Permalink to this headline">¶</a></h3>
<p>Collector posses all the attributes of PolycyclicGroup, In addition there are
few more attributes which are defined below:</p>
<ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">free_group</span></code> : free_group provides the mapping of polycyclic generating sequence with
the free group elements.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">pc_presentation</span></code> : Provides the presentation of polycyclic groups with the
help of power and conjugate relators.</p></li>
</ul>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">Collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">Collector</span><span class="o">.</span><span class="n">free_group</span>
<span class="go">&lt;free group on the generators (x0, x1)&gt;</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">Collector</span><span class="o">.</span><span class="n">pc_presentation</span>
<span class="go">{x0**2: (), x1**3: (), x0**-1*x1*x0: x1**2}</span>
</pre></div>
</div>
</section>
<section id="computation-of-minimal-uncollected-subword">
<h3>Computation of Minimal Uncollected Subword<a class="headerlink" href="#computation-of-minimal-uncollected-subword" title="Permalink to this headline">¶</a></h3>
<p>A word <code class="docutils literal notranslate"><span class="pre">V</span></code> defined on generators in the free_group of pc_group is a minimal
uncollected subword of the word <code class="docutils literal notranslate"><span class="pre">W</span></code> if <code class="docutils literal notranslate"><span class="pre">V</span></code> is a subword of <code class="docutils literal notranslate"><span class="pre">W</span></code> and it has one of
the following form:</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(v = {x_{i+1}}^{a_j}x_i\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(v = {x_{i+1}}^{a_j}{x_i}^{-1}\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(v = {x_i}^{a_j}\)</span></p></li>
</ul>
<p><span class="math notranslate nohighlight">\(a_j \notin \{0, \ldots \mathrm{relative\_order}[j]-1\}\)</span>.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.free_groups</span> <span class="kn">import</span> <span class="n">free_group</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">x1</span><span class="p">,</span> <span class="n">x2</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;x1, x2&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">word</span> <span class="o">=</span> <span class="n">x2</span><span class="o">**</span><span class="mi">2</span><span class="o">*</span><span class="n">x1</span><span class="o">**</span><span class="mi">7</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span><span class="o">.</span><span class="n">minimal_uncollected_subword</span><span class="p">(</span><span class="n">word</span><span class="p">)</span>
<span class="go">((x2, 2),)</span>
</pre></div>
</div>
</section>
<section id="computation-of-subword-index">
<h3>Computation of Subword Index<a class="headerlink" href="#computation-of-subword-index" title="Permalink to this headline">¶</a></h3>
<p>For a given word and it’s subword, subword_index computes the
starting and ending index of the subword in the word.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.free_groups</span> <span class="kn">import</span> <span class="n">free_group</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">x1</span><span class="p">,</span> <span class="n">x2</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;x1, x2&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">word</span> <span class="o">=</span> <span class="n">x2</span><span class="o">**</span><span class="mi">2</span><span class="o">*</span><span class="n">x1</span><span class="o">**</span><span class="mi">7</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">w</span> <span class="o">=</span> <span class="n">x2</span><span class="o">**</span><span class="mi">2</span><span class="o">*</span><span class="n">x1</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span><span class="o">.</span><span class="n">subword_index</span><span class="p">(</span><span class="n">word</span><span class="p">,</span> <span class="n">w</span><span class="p">)</span>
<span class="go">(0, 3)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">w</span> <span class="o">=</span> <span class="n">x1</span><span class="o">**</span><span class="mi">7</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span><span class="o">.</span><span class="n">subword_index</span><span class="p">(</span><span class="n">word</span><span class="p">,</span> <span class="n">w</span><span class="p">)</span>
<span class="go">(2, 9)</span>
</pre></div>
</div>
</section>
<section id="computation-of-collected-word">
<h3>Computation of Collected Word<a class="headerlink" href="#computation-of-collected-word" title="Permalink to this headline">¶</a></h3>
<p>A word <code class="docutils literal notranslate"><span class="pre">W</span></code> is called collected, if <code class="docutils literal notranslate"><span class="pre">W</span></code> <span class="math notranslate nohighlight">\(= {x_{i_1}}^{a_1} \ldots {x_{i_r}}^{a_r}\)</span>
with <span class="math notranslate nohighlight">\(i_1 &lt; i_2&lt; \ldots &lt; i_r\)</span> and <span class="math notranslate nohighlight">\(a_j\)</span> is in <span class="math notranslate nohighlight">\(\{1 \ldots s_{j-1}\}\)</span>, where <span class="math notranslate nohighlight">\(s_j\)</span>
represents the respective relative order.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.perm_groups</span> <span class="kn">import</span> <span class="n">PermutationGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.free_groups</span> <span class="kn">import</span> <span class="n">free_group</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">x0</span><span class="p">,</span> <span class="n">x1</span><span class="p">,</span> <span class="n">x2</span><span class="p">,</span> <span class="n">x3</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;x0, x1, x2, x3&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">word</span> <span class="o">=</span> <span class="n">x3</span><span class="o">*</span><span class="n">x2</span><span class="o">*</span><span class="n">x1</span><span class="o">*</span><span class="n">x0</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collected_word</span> <span class="o">=</span> <span class="n">collector</span><span class="o">.</span><span class="n">collected_word</span><span class="p">(</span><span class="n">word</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">free_to_perm</span> <span class="o">=</span> <span class="p">{}</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">free_group</span> <span class="o">=</span> <span class="n">collector</span><span class="o">.</span><span class="n">free_group</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">for</span> <span class="n">sym</span><span class="p">,</span> <span class="n">gen</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">free_group</span><span class="o">.</span><span class="n">symbols</span><span class="p">,</span> <span class="n">collector</span><span class="o">.</span><span class="n">pcgs</span><span class="p">):</span>
<span class="gp">... </span>    <span class="n">free_to_perm</span><span class="p">[</span><span class="n">sym</span><span class="p">]</span> <span class="o">=</span> <span class="n">gen</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G1</span> <span class="o">=</span> <span class="n">PermutationGroup</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">for</span> <span class="n">w</span> <span class="ow">in</span> <span class="n">word</span><span class="p">:</span>
<span class="gp">... </span>    <span class="n">sym</span> <span class="o">=</span> <span class="n">w</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="gp">... </span>    <span class="n">perm</span> <span class="o">=</span> <span class="n">free_to_perm</span><span class="p">[</span><span class="n">sym</span><span class="p">]</span>
<span class="gp">... </span>    <span class="n">G1</span> <span class="o">=</span> <span class="n">PermutationGroup</span><span class="p">([</span><span class="n">perm</span><span class="p">]</span> <span class="o">+</span> <span class="n">G1</span><span class="o">.</span><span class="n">generators</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G2</span> <span class="o">=</span> <span class="n">PermutationGroup</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">for</span> <span class="n">w</span> <span class="ow">in</span> <span class="n">collected_word</span><span class="p">:</span>
<span class="gp">... </span>    <span class="n">sym</span> <span class="o">=</span> <span class="n">w</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="gp">... </span>    <span class="n">perm</span> <span class="o">=</span> <span class="n">free_to_perm</span><span class="p">[</span><span class="n">sym</span><span class="p">]</span>
<span class="gp">... </span>    <span class="n">G2</span> <span class="o">=</span> <span class="n">PermutationGroup</span><span class="p">([</span><span class="n">perm</span><span class="p">]</span> <span class="o">+</span> <span class="n">G2</span><span class="o">.</span><span class="n">generators</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G1</span> <span class="o">==</span> <span class="n">G2</span>
<span class="go">True</span>
</pre></div>
</div>
</section>
</section>
<section id="computation-of-polycyclic-presentation">
<h2>Computation of Polycyclic Presentation<a class="headerlink" href="#computation-of-polycyclic-presentation" title="Permalink to this headline">¶</a></h2>
<p>The computation of presentation starts from the bottom of the pcgs and polycyclic series.
Storing all the previous generators from pcgs and then taking the last generator
as the generator which acts as a conjugator and conjugates all the previous
generators in the list.</p>
<p>To get a clear picture, start with an example of SymmetricGroup(4). For S(4) there are 4
generators in pcgs say <span class="math notranslate nohighlight">\([x_0, x_1, x_2, x_3]\)</span> and the relative_order vector is [2, 3, 2, 2].
Starting from bottom of this sequence the presentation is computed in order as below.</p>
<p>using only <span class="math notranslate nohighlight">\([x_3]\)</span> from <code class="docutils literal notranslate"><span class="pre">pcgs</span></code> and <code class="docutils literal notranslate"><span class="pre">pc_series[4]</span></code> compute:</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(x_3^2\)</span></p></li>
</ul>
<p>using only <span class="math notranslate nohighlight">\([x_3]\)</span> from <code class="docutils literal notranslate"><span class="pre">pcgs</span></code> and <code class="docutils literal notranslate"><span class="pre">pc_series[3]</span></code> compute:</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(x_2^2\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(x_2^{-1}x_3x_2\)</span></p></li>
</ul>
<p>using <span class="math notranslate nohighlight">\([x_3, x_2]\)</span> from <code class="docutils literal notranslate"><span class="pre">pcgs</span></code> and <code class="docutils literal notranslate"><span class="pre">pc_series[2]</span></code> compute:</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(x_1^3\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(x_1^{-1}x_3x_1\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(x_1^{-1}x_2x_1\)</span></p></li>
</ul>
<p>using <span class="math notranslate nohighlight">\([x_3, x_2, x_1]\)</span> from <code class="docutils literal notranslate"><span class="pre">pcgs</span></code> and <code class="docutils literal notranslate"><span class="pre">pc_series[1]</span></code> compute:</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(x_0^2\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(x_0^{-1}x_3x_0\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(x_0^{-1}x_2x_0\)</span></p></li>
<li><p><span class="math notranslate nohighlight">\(x_0^{-1}x_1x_0\)</span></p></li>
</ul>
<p>One thing to note is same group can have different pcgs due to variying derived_series which,
results in different polycyclic presentations.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.permutations</span> <span class="kn">import</span> <span class="n">Permutation</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">pcgs</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">pcgs</span>
<span class="gp">&gt;&gt;&gt; </span><span class="nb">len</span><span class="p">(</span><span class="n">pcgs</span><span class="p">)</span>
<span class="go">4</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">free_group</span> <span class="o">=</span> <span class="n">collector</span><span class="o">.</span><span class="n">free_group</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">pc_resentation</span> <span class="o">=</span> <span class="n">collector</span><span class="o">.</span><span class="n">pc_presentation</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">free_to_perm</span> <span class="o">=</span> <span class="p">{}</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">for</span> <span class="n">s</span><span class="p">,</span> <span class="n">g</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">free_group</span><span class="o">.</span><span class="n">symbols</span><span class="p">,</span> <span class="n">pcgs</span><span class="p">):</span>
<span class="gp">... </span>    <span class="n">free_to_perm</span><span class="p">[</span><span class="n">s</span><span class="p">]</span> <span class="o">=</span> <span class="n">g</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">pc_resentation</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
<span class="gp">... </span>    <span class="n">k_array</span> <span class="o">=</span> <span class="n">k</span><span class="o">.</span><span class="n">array_form</span>
<span class="gp">... </span>    <span class="k">if</span> <span class="n">v</span> <span class="o">!=</span> <span class="p">():</span>
<span class="gp">... </span>       <span class="n">v_array</span> <span class="o">=</span> <span class="n">v</span><span class="o">.</span><span class="n">array_form</span>
<span class="gp">... </span>    <span class="n">lhs</span> <span class="o">=</span> <span class="n">Permutation</span><span class="p">()</span>
<span class="gp">... </span>    <span class="k">for</span> <span class="n">gen</span> <span class="ow">in</span> <span class="n">k_array</span><span class="p">:</span>
<span class="gp">... </span>        <span class="n">s</span> <span class="o">=</span> <span class="n">gen</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="gp">... </span>        <span class="n">e</span> <span class="o">=</span> <span class="n">gen</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
<span class="gp">... </span>        <span class="n">lhs</span> <span class="o">=</span> <span class="n">lhs</span><span class="o">*</span><span class="n">free_to_perm</span><span class="p">[</span><span class="n">s</span><span class="p">]</span><span class="o">**</span><span class="n">e</span>
<span class="gp">... </span>    <span class="k">if</span> <span class="n">v</span> <span class="o">==</span> <span class="p">():</span>
<span class="gp">... </span>        <span class="k">assert</span> <span class="n">lhs</span><span class="o">.</span><span class="n">is_identity</span>
<span class="gp">... </span>        <span class="k">continue</span>
<span class="gp">... </span>    <span class="n">rhs</span> <span class="o">=</span> <span class="n">Permutation</span><span class="p">()</span>
<span class="gp">... </span>    <span class="k">for</span> <span class="n">gen</span> <span class="ow">in</span> <span class="n">v_array</span><span class="p">:</span>
<span class="gp">... </span>        <span class="n">s</span> <span class="o">=</span> <span class="n">gen</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="gp">... </span>        <span class="n">e</span> <span class="o">=</span> <span class="n">gen</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
<span class="gp">... </span>        <span class="n">rhs</span> <span class="o">=</span> <span class="n">rhs</span><span class="o">*</span><span class="n">free_to_perm</span><span class="p">[</span><span class="n">s</span><span class="p">]</span><span class="o">**</span><span class="n">e</span>
<span class="gp">... </span>    <span class="k">assert</span> <span class="n">lhs</span> <span class="o">==</span> <span class="n">rhs</span>
</pre></div>
</div>
</section>
<section id="computation-of-exponent-vector">
<h2>Computation of Exponent Vector<a class="headerlink" href="#computation-of-exponent-vector" title="Permalink to this headline">¶</a></h2>
<p>Any generator of the polycyclic group can be represented with the help of it’s
polycyclic generating sequence. Hence, the length of exponent vector is equal to
the length of the pcgs.</p>
<p>A given generator <code class="docutils literal notranslate"><span class="pre">g</span></code> of the polycyclic group, can be represented as
<span class="math notranslate nohighlight">\(g = x_1^{e_1} \ldots x_n^{e_n}\)</span>, where <span class="math notranslate nohighlight">\(x_i\)</span> represents polycyclic generators
and <code class="docutils literal notranslate"><span class="pre">n</span></code> is the number of generators in the free_group equal to the length of pcgs.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.permutations</span> <span class="kn">import</span> <span class="n">Permutation</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">pcgs</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">pcgs</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span><span class="o">.</span><span class="n">exponent_vector</span><span class="p">(</span><span class="n">G</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
<span class="go">[1, 0, 0, 0]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">exp</span> <span class="o">=</span> <span class="n">collector</span><span class="o">.</span><span class="n">exponent_vector</span><span class="p">(</span><span class="n">G</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">g</span> <span class="o">=</span> <span class="n">Permutation</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">exp</span><span class="p">)):</span>
<span class="gp">... </span>    <span class="n">g</span> <span class="o">=</span> <span class="n">g</span><span class="o">*</span><span class="n">pcgs</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">**</span><span class="n">exp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="k">if</span> <span class="n">exp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="k">else</span> <span class="n">g</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">assert</span> <span class="n">g</span> <span class="o">==</span> <span class="n">G</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
</pre></div>
</div>
<section id="depth-of-polycyclic-generator">
<h3>Depth of Polycyclic generator<a class="headerlink" href="#depth-of-polycyclic-generator" title="Permalink to this headline">¶</a></h3>
<p>Depth of a given polycyclic generator is defined as the index of the first
non-zero entry in the exponent vector.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span><span class="o">.</span><span class="n">depth</span><span class="p">(</span><span class="n">G</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
<span class="go">2</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span><span class="o">.</span><span class="n">depth</span><span class="p">(</span><span class="n">G</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
<span class="go">1</span>
</pre></div>
</div>
</section>
<section id="computation-of-leading-exponent">
<h3>Computation of Leading Exponent<a class="headerlink" href="#computation-of-leading-exponent" title="Permalink to this headline">¶</a></h3>
<p>Leading exponent represents the exponent of polycyclic generator at the above depth.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.named_groups</span> <span class="kn">import</span> <span class="n">SymmetricGroup</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">SymmetricGroup</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">PcGroup</span> <span class="o">=</span> <span class="n">G</span><span class="o">.</span><span class="n">polycyclic_group</span><span class="p">()</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span> <span class="o">=</span> <span class="n">PcGroup</span><span class="o">.</span><span class="n">collector</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">collector</span><span class="o">.</span><span class="n">leading_exponent</span><span class="p">(</span><span class="n">G</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
<span class="go">1</span>
</pre></div>
</div>
</section>
</section>
<section id="bibliography">
<h2>Bibliography<a class="headerlink" href="#bibliography" title="Permalink to this headline">¶</a></h2>
<dl class="citation">
<dt class="label" id="ho05"><span class="brackets">Ho05</span></dt>
<dd><p>Derek F. Holt,
Handbook of Computational Group Theory.
In the series ‘Discrete Mathematics and its Applications’,
<a class="reference external" href="https://www.crcpress.com/Handbook-of-Computational-Group-Theory/Holt-Eick-OBrien/p/book/9781584883722">Chapman &amp; Hall/CRC 2005, xvi + 514 p</a>.</p>
</dd>
</dl>
</section>
</section>


            <div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="../../index.html">
              <img class="logo" src="../../_static/sympylogo.png" alt="Logo"/>
            </a></p>
  <h3><a href="../../index.html">Table of Contents</a></h3>
  <ul>
<li><a class="reference internal" href="#">Polycyclic Groups</a><ul>
<li><a class="reference internal" href="#introduction">Introduction</a><ul>
<li><a class="reference internal" href="#overview-of-functionalities">Overview of functionalities</a></li>
</ul>
</li>
<li><a class="reference internal" href="#the-construction-of-polycyclic-groups">The Construction of Polycyclic Groups</a><ul>
<li><a class="reference internal" href="#attributes-of-polycyclicgroup">Attributes of PolycyclicGroup</a></li>
</ul>
</li>
<li><a class="reference internal" href="#the-construction-of-collector">The Construction of Collector</a><ul>
<li><a class="reference internal" href="#attributes-of-collector">Attributes of Collector</a></li>
<li><a class="reference internal" href="#computation-of-minimal-uncollected-subword">Computation of Minimal Uncollected Subword</a></li>
<li><a class="reference internal" href="#computation-of-subword-index">Computation of Subword Index</a></li>
<li><a class="reference internal" href="#computation-of-collected-word">Computation of Collected Word</a></li>
</ul>
</li>
<li><a class="reference internal" href="#computation-of-polycyclic-presentation">Computation of Polycyclic Presentation</a></li>
<li><a class="reference internal" href="#computation-of-exponent-vector">Computation of Exponent Vector</a><ul>
<li><a class="reference internal" href="#depth-of-polycyclic-generator">Depth of Polycyclic generator</a></li>
<li><a class="reference internal" href="#computation-of-leading-exponent">Computation of Leading Exponent</a></li>
</ul>
</li>
<li><a class="reference internal" href="#bibliography">Bibliography</a></li>
</ul>
</li>
</ul>

  <h4>Previous topic</h4>
  <p class="topless"><a href="fp_groups.html"
                        title="previous chapter">Finitely Presented Groups</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="../concrete.html"
                        title="next chapter">Concrete</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../../_sources/modules/combinatorics/pc_groups.rst.txt"
            rel="nofollow">Show Source</a></li>
    </ul>
   </div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="https://docs.sympy.org/latest/search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="../concrete.html" title="Concrete"
             >next</a> |</li>
        <li class="right" >
          <a href="fp_groups.html" title="Finitely Presented Groups"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="index.html" >Combinatorics</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Polycyclic Groups</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2021 SymPy Development Team.
      Last updated on Sep 30, 2021.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.1.2.
    </div>
  </body>

<!-- Mirrored from docs.sympy.org/latest/modules/combinatorics/pc_groups.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:28:19 GMT -->
</html>